/**
 * \file
 */
#include "precompiled.hpp"
#include "kfs.hpp"
#include "kfs_allocator.hpp"
#include "kfs_cache.hpp"
#include "kfs_file_descriptor.hpp"
#include "kfs_impl.hpp"
#include "kfs_time.hpp"
#include "Exception.hpp"
#include <boost/algorithm/string/classification.hpp>
#include <boost/algorithm/string/iter_find.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/scoped_array.hpp>
#include <errno.h>
#include <fcntl.h>
#include <sys/stat.h>                   // S_ISDIR et al
#include <fstream>
#include <map>
#include <memory>
#include <string>
#include <vector>

using std::auto_ptr;
using std::ios;  using std::fstream;
using std::make_pair;
using std::string;  using std::vector;

block_index_t const blockid_nil = 0;

//static int32_t floorLog2(uint32_t n)
//{
//    if (n == 0)
//        return -1;
//
//    int32_t pos = 0;
//    if (n >= (1 <<16)) { n >>= 16; pos += 16; }
//    if (n >= (1 << 8)) { n >>=  8; pos +=  8; }
//    if (n >= (1 << 4)) { n >>=  4; pos +=  4; }
//    if (n >= (1 << 2)) { n >>=  2; pos +=  2; }
//    if (n >= (1 << 1)) {           pos +=  1; }
//    return pos;
//}


//----------------------------- kfs::SuperBlock -----------------------------//

uint32_t MasterBlock::Magic = ('k' << 24) | ('f' << 16) | ('s' << 8) | '!';

//------------------------------- kfs::Inode -------------------------------//

uint32_t Inode::Magic = ('d' << 24) | ('o' << 16) | ('n' << 8) | 'I';

//-------------------------------- kfs::Impl --------------------------------//


kfs::Impl::Impl()
{
    bitmapDiskBlockNum = 1;
    // Inode of the root directory: location is fixed.
    rootBlockNum = 2;
}


void kfs::Impl::file_getIndices(uint32_t fileBlockNumber,
        std::vector<uint32_t>& indices)
{
    indices.clear();
    // How many block pointers in each index block?
    // Example: A 4 KB index block holds 1024 32-bit pointers.
    uint32_t const n = mb.blockNumBytes / sizeof(uint32_t);
    unsigned const log_n = floor_log2(n);
    //uint32_t const mask_low  = (1 << floorLog2(n)) - 1;
    uint32_t const mask_low  = n - 1;
    if(fileBlockNumber >= n*n + n + 12)
    {
        // Triple indirection
        uint32_t acc = fileBlockNumber - n*n - n - 12;
        indices.push_back(14);
        indices.push_back((acc >> (2*log_n)) & mask_low);
        indices.push_back((acc >> log_n)     & mask_low);
        indices.push_back( acc               & mask_low);
    }
    else if(fileBlockNumber >= n + 12)
    {
        // Double indirection
        uint32_t acc = fileBlockNumber - n - 12;
        indices.push_back(13);
        indices.push_back((acc >> log_n) & mask_low);
        indices.push_back( acc           & mask_low);
    }
    else if(fileBlockNumber >= 12)
    {
        // Single indirection
        indices.push_back(12);
        indices.push_back(fileBlockNumber - 12);
    }
    else
    {
        // Zero indirection
        indices.push_back(fileBlockNumber);
    }
}


FileDescriptor*
kfs::Impl::inode_create(FileDescriptor* parent,
    kfs* fs, string const& path,
    string const& name, int flags,
    mode_t mode, uid_t userID, gid_t groupID )
{
    // Time stamp
    uint64_t timeNowNsec = KfsTime::timeNow();
    // Allocate a block for the new inode.
    AllocBlockRef childBlock = disk_allocate();

    // Create a cache entry for the new inode.
    InodeCache::value_type elt(
        path,
        boost::shared_ptr<CacheInode>(new CacheInode())
    );
    CacheInode& child = *elt.second;
    child.blockNum = childBlock.get();
    child.inode.sizeNumBytes = 0;
    child.inode.userID = userID;
    child.inode.groupID = groupID;
    child.inode.mode = mode;
    child.inode.ctime = timeNowNsec;
    child.inode.mtime = timeNowNsec;
    child.inode.atime = timeNowNsec;
    child.inode.linkCount = 1;
    child.inode.dataBlockAddresses.resize(15);

    // Write the inode to disk.
    boost::scoped_array<uint8_t> block(createBlockBuffer());
    serialize(child.inode, block.get());
    kfs_disk_write(*this, child.blockNum, block.get());

    // Open the new file using the in-memory inode.
    std::auto_ptr<FileDescriptor> file(new FileDescriptor(fs, flags));
    file->inodeRef.reset(cache_add_from_memory(elt));

    if( S_ISDIR(mode) )
    {
        // Create a parent entry
        dir_add(file.get(), "..", parent->inodeRef->elt->second->blockNum);
        // Create a self entry
        dir_add(file.get(), ".", child.blockNum);
    }
    try
    {
        dir_add(parent, name, child.blockNum);
        // Commit the allocation.
        childBlock.release();
        // Relinquish the new descriptor to the caller.
        return file.release();
    }
    catch(Exception& e)
    {
        throw;
    }
}


InodeRef*
kfs::Impl::traverse(string const& arg_path, kfs* fs)
{
    // Create a file descriptor in order to read directories.
    boost::scoped_ptr<FileDescriptor> dir(
        fs->file_open(rootBlockNum, "/", O_RDONLY));

    string path = arg_path;
    if(path.empty() || path[0] != '/')
    {
        // Path must begin with a slash.
        throw Error(EINVAL,"Not an absolute path: %s", arg_path.c_str());
    }
    // Trim the leading slash, as it is excluded from dir_find().  We already
    // have the root directory.
    path.erase(path.begin());
    // Trim the trailing slash, if any. It messes up the split. It might also
    // get into the inode cache, causing duplicate entries to the same inode.
    if(path.size() > 1 && *(--path.end()) == '/')
        path.erase(--path.end());

    using namespace boost::algorithm;
    using boost::copy_range;
    typedef split_iterator<string::iterator> string_split_iterator;
    for(string_split_iterator iter =
        make_split_iterator(path, first_finder("/", is_equal()));
        iter != string_split_iterator();
        ++iter)
    {
        string const dirEntryName = copy_range<string>(*iter);
        string prefix(path.begin(), iter->end());
        prefix = "/" + prefix;
        printf("  %-8s  %s\n", dirEntryName.c_str(), prefix.c_str());

        // Look in the directory.  Throw if not found.
        DirIter dirIter;
        dir_find(dir.get(), dirEntryName, &dirIter);
        dir.reset(fs->file_open(dirIter.blockNum, prefix.c_str(), O_RDONLY));
    }

    auto_ptr<InodeRef> inodeRef(new InodeRef);
    CacheInode const& inodeNode = *dir->inodeRef->elt->second;
    inodeRef->diskBlockNum = inodeNode.blockNum;
    inodeRef->inode = inodeNode.inode;

    return inodeRef.release();

    /* Alternate method: split before processing
    vector<string> entries;
    split(entries, path, is_any_of("/"), token_compress_on);
    printf("%u entries:\n", entries.size());
    for(vector<string>::const_iterator i = entries.begin();
        i != entries.end(); ++i)
    {
        printf("  `%s' ", i->c_str());
    }
    printf("\n\n");
    */
}


void
kfs_path_split(
    string const& path,
    string& parentPath,
    string& childName
)
{
    if(path.empty() || path[0] != '/')
    {
        // Path must begin with a slash.
        throw Error(EINVAL,"Not an absolute path: %s", path.c_str());
    }
    // Strip the trailing separator, if any.
    string::size_type end;
    if( path.size() >= 2 && *(path.end()-1) == '/' )
        end = path.size() - 1;
    else
        end = path.size();
    size_t i = path.rfind('/', end - 1);
    if(i == string::npos)
    {
        // Path must contain at least one slash.
        throw Error(EINVAL,"Not an absolute path: %s", path.c_str());
    }
    // Split the path into two components. parentPath always gets a
    // trailing separator.
    ++i;
    // I points to the start of the child name.
    parentPath = path.substr(0, i);
    childName = path.substr(i, end-i);

    /* Debug output
    printf("`%s'  `%s'   i=%2d  end=%2d\n",
        parentPath.c_str(), childName.c_str(), i, end);
    */
}
